#include<conio.h>
#include<malloc.h>
#include<iostream>

using namespace std;
#define order 4											
typedef struct nodestruct
{
	int key[order];										
	struct nodestruct *index_ptr[order+1];				
	int fill_fact;	
	struct nodestruct *parent;							
	
}bnode ;												

class  btree
{
	bnode *root;																		
public:
	void init(bnode* new_node);	
	void initr();							 
	void display();	
	bnode* show(bnode *t);
	void showchild(bnode* t);
	//INSERT
		int insert(int key);
		bnode* sortarray(bnode* cur,int key);	
		bnode* search_leaf(bnode* t,int key);
		void sortedentry(bnode* cur,int key);
		void sortarray1(bnode* cur,int key,int *arr);
		bnode* par_nul(bnode* t1,bnode* t2,bnode* c,int mid_val);
		bnode* par_space(bnode* t1,bnode* t2,bnode* c,int mid_val);
		bnode* par_full(bnode* t1,bnode* t2,bnode* c,int mid_val);
	//DELETE
	bnode* search_node(bnode* t,int key);
	int delete_key(int key);
	void rytdistribute(bnode* target,bnode* sibling,int pos);
    void lftdistribute(bnode* target,bnode* sibling,int pos);
    int rytmerge(bnode* target,bnode* sibling,int pos);
    int lftmerge(bnode* target,bnode* sibling,int pos);
     int chek_del(int po,bnode* t_l);
     int splmerge(int pc,bnode* p);


	
};
/*INSERT SE RELATED FUNCTION*/
void btree::init(bnode *new_node)
{
	
	new_node->fill_fact = 0;
	new_node->parent = NULL;
	int i;
	for(i=0;i<=order;i++)
		new_node->index_ptr[i] =NULL;
	for(i=0;i<order;i++)
		new_node->key[i] =-1;
	
}
void btree::initr()
{
	root =(bnode*)malloc(sizeof(bnode));
	root->fill_fact = 0;
	root->parent = NULL;
	int i;
	for(i=0;i<=order;i++)
		root->index_ptr[i] =NULL;
	for(i=0;i<order;i++)
		root->key[i] =-1;
}
bnode* btree::search_leaf(bnode* current_node,int key)
{
	int i;
	if(current_node->index_ptr[0] == NULL)
	{
		
		return current_node;
	
	}
	else
	{
		bnode *c= NULL;
		if(current_node->fill_fact == 1)
		{
			if(key<current_node->key[0])
			{
				current_node = current_node->index_ptr[0];
				c = search_leaf(current_node,key);
				return c;
			}
			else
			{
				current_node = current_node->index_ptr[1];
				c = search_leaf(current_node,key);
				return c;
			}
		}
		else
		{
			for(i=0;i<(current_node->fill_fact-1);i++)
			{
				if(key<current_node->key[i])
				{
					current_node = current_node->index_ptr[i];
					c=search_leaf(current_node,key);
					return c;
				}
				else
				{
					if(key>current_node->key[i] && key<current_node->key[i+1])
					{
						current_node = current_node->index_ptr[i+1];
						c=search_leaf(current_node,key);
						return c;
					}
				}
			}
			if(key<current_node->key[i])
			{
				current_node = current_node->index_ptr[i];
				c=search_leaf(current_node,key);
				return c;
			}
			else
			{
				current_node = current_node->index_ptr[i+1];
				c=search_leaf(current_node,key);
				return c;
			}
		}
	}
}


void btree::sortedentry(bnode* cur,int key)
{
	int temp_key1 = key;
	int temp_key2= key;
	int i;
	for(i=0;i<cur->fill_fact;i++)
		{
			if(temp_key1 < (cur->key[i]))
				{
					temp_key2 = temp_key1;
					temp_key1 = cur->key[i];
					cur->key[i] = temp_key2;
				}
		}
	cur->key[i] = temp_key1;
	cur->fill_fact ++ ;
		
}
void btree::sortarray1(bnode* cur,int key, int *arr)
{
	int temp_key1,temp_key2,i;
	temp_key1=temp_key2=key;
	for(i=0;i<order;i++)
	{
		if(temp_key1 < (cur->key[i]))
		{
			temp_key2 = temp_key1;
			temp_key1 = cur->key[i];
			*(arr+i) = temp_key2;
		}
		else
		{
			*(arr+i) = cur->key[i];
		}
	}
	*(arr+i) = temp_key1;
}
bnode* btree::par_nul(bnode* t1,bnode* t2,bnode* c,int mid_val)
{
	c->index_ptr[0] = t1;
	c->index_ptr[1] = t2;
	c->key[0]= mid_val;
	int i;
	for(i=1;i<order;i++)
	{
			c->key[i] = -1;
	}
	c->fill_fact=1;
	t1->parent = c;
	t2->parent = c;
	return c;

}
bnode* btree::par_space(bnode* t1,bnode* t2,bnode* c,int mid_val)
{

	int i,f,pos;
	bnode* p;
	p = c->parent;
	f = p->fill_fact;
	for(i=0;i<=f;i++)
	{
			if(p->index_ptr[i] == c)
			{
				break;
			}
	}
	pos = i;
	if(pos == 0)
	{
			for(i=f;i>0;i--)
			{
				p->key[i] = p->key[i-1];
			}
			p->key[0] = mid_val;
			for(i=f+1;i>1;i--)
			{
				p->index_ptr[i] = p->index_ptr[i-1];
			}
			p->index_ptr[0] = t1;
			p->index_ptr[1] = t2;
			t1->parent =p;
			t2->parent = p;
			p->fill_fact++;
			return p;
	}
	else if(pos == (order-1))
	{
			p->key[order-1] = mid_val;
			p->index_ptr[order-1] = t1;
			p->index_ptr[order] = t2;
			t1->parent = p;
			t2->parent = p;
			p->fill_fact++;
			return p;
	}
	else
	{
		for(i=f;i>pos;i--)
			{
				p->key[i] = p->key[i-1];
			}
			p->key[pos] = mid_val;
			for(i=f+1;i>pos+1;i--)
			{
				p->index_ptr[i] = p->index_ptr[i-1];
			}
			p->index_ptr[pos] = t1;
			p->index_ptr[pos+1] = t2;
			t1->parent = p;
			t2->parent = p;
			p->fill_fact ++;
		
			return p;

	}
}
bnode* btree::par_full(bnode* t1,bnode* t2,bnode* c,int mid_val)
{
	int pos,i,j;
	int mid = (order+1)/2;
	bnode* t = c->parent;
	for(i=0;i<=order;i++)
	{
			if(t->index_ptr[i] == c)
				break;
	}
	pos =i;
	int *b=new int[order+1];
	sortarray1(t,mid_val,b);
	int mid_valb=*(b+mid);
	bnode* new1 = (bnode*)malloc(sizeof(bnode));
	init(new1);
	for(i=0;i<mid;i++)
	{
			new1->key[i]=*(b+i);
	}
	new1->fill_fact = i;
	bnode* new2 = (bnode*)malloc(sizeof(bnode));
	init(new2);
	for(i=mid+1,j=0;i<=order;i++,j++)
	{
			new2->key[j] = *(b+i);
	}
	new2->fill_fact=j;
	delete[] b;
	if(pos < mid)
	{
		for(i=0;i<=(new1->fill_fact);i++)
			{
				if(i==pos)
				{
					new1->index_ptr[i]=t1;
					t1->parent = new1;
				}
				else if( i == pos+1)
				{
					new1->index_ptr[i] = t2;
					t2->parent =new1;
				}
				else if(i>pos)
				{
					new1->index_ptr[i] = t->index_ptr[i-1];
					t->index_ptr[i-1]->parent = new1;
				}
				else
				{
					new1->index_ptr[i] = t->index_ptr[i];
					t->index_ptr[i]->parent = new1;
				}
			}
			for(i=0,j=mid;i<=(new2->fill_fact) && j<=order;i++,j++)
			{
				new2->index_ptr[i] = t->index_ptr[j];
				t->index_ptr[j]->parent = new2;
			}

		}
		else if(pos == mid)
		{
			for(i=0;i<mid;i++)
			{
				new1->index_ptr[i] = t->index_ptr[i];
				t->index_ptr[i]->parent = new1;
			}
			new1->index_ptr[i] = t1;
			t1->parent = new1;
			new2->index_ptr[0] = t2;
			t2->parent = new2;
			for(i=1,j=mid+1;i<=new2->fill_fact;i++,j++)
			{
				new2->index_ptr[i] = t->index_ptr[j];
				t->index_ptr[j]->parent = new2;
			}

		}
		else
		{
			for(i=0;i<=mid;i++)
			{
				new1->index_ptr[i] = t->index_ptr[i];
				t->index_ptr[i]->parent = new1;
			}
			for(i=new2->fill_fact;i>=0;i--)
			{
				if(i == new2->fill_fact)
					{
                        new2->index_ptr[i] = t2;
                        t2->parent = new2;
                        }
				else if(i == (new2->fill_fact -1))
					{
                          new2->index_ptr[i] = t1;
                          t1->parent = new2;
                          }
				else
					{
                          new2->index_ptr[i] = t->index_ptr[order-1];
                          t->index_ptr[order-1]->parent = new2;
                          }
			}

			
		}
		if(t->parent == NULL)
		{
			bnode* pp= (bnode*)malloc(sizeof(bnode*)) ;
		    init(pp);
			pp->key[0] =mid_valb;
			pp->fill_fact=1;
			pp->parent =NULL;
			pp->index_ptr[0] = new1;
			pp->index_ptr[1] = new2;
			new1->parent =  new2->parent = pp;
			root = pp;
			return pp;

		}
		else
		{
			if(t->parent->fill_fact < order)
			{
				bnode* r = par_space(new1,new2,t,mid_valb);
				return r;
			}
			else
			{
				bnode* r = par_full(new1,new2,t,mid_valb);
				return r;
			}

		}

}

bnode* btree::sortarray(bnode* cur,int key)
{
	int mid = (int)((order+1)/2);
	int *a = new int[order+1];
	sortarray1(cur,key,a);
	int mid_val = *(a + mid);
	int i,j;
	bnode* temp_node1 = (bnode*)malloc(sizeof(bnode));
	init(temp_node1);
	bnode* temp_node2 = (bnode*)malloc(sizeof(bnode));
	init(temp_node2);
	for(i=0;i<mid;i++)
	{
		temp_node1->key[i] = *(a+i);
	}
	temp_node1->fill_fact = i;
	for(i=mid,j=0;i<=order && j<order;i++,j++)
	{
			temp_node2->key[j] = *(a+i);
	}
	temp_node2->fill_fact = j;
	delete[] a;
	
	//propogation


	if(cur->parent == NULL)
	{
		bnode *res = par_nul(temp_node1,temp_node2,cur,mid_val);
		return res;
	}
	else if(cur->parent->fill_fact == order)
	{
		bnode* res = par_full(temp_node1,temp_node2,cur,mid_val);
		return res;
		
		
	}

	else
	{
		
		bnode* res=par_space(temp_node1,temp_node2,cur,mid_val);
		return res;
		
	}

}


int btree::insert(int key)
{
	bnode* target_node = search_leaf(root,key);
	
	if(target_node->fill_fact < order)
	{
			if(target_node->fill_fact == 0)
			{     
				target_node->key[0] = key;
				target_node->fill_fact++;
				return 0;
				
			}
			else 
			{
				
				sortedentry(target_node,key);
				return 0;
			}
	}
	else
	{
		//SORT THE KEY & NODE VALUES
		
		bnode *p = sortarray(target_node,key);
		return 0;
	}
	
}
/*------------------------------------------------------------------------*/
bnode* btree::search_node(bnode *t, int key)
{
	int i,p;
	int f = t->fill_fact;
	for(i=0;i<f;i++)
	{
                    if(t->key[i] == key)
                    return t;
    }
    if(t->parent == NULL)
    return NULL;
    else 
    {
    bnode* r;
    r=search_node(t->parent,key);
    return r;
    }
                                 
}
void btree::rytdistribute(bnode* target,bnode* sibling,int pos)
{
	int tf= target->fill_fact;
	target->key[tf] = sibling->key[0];
	target->fill_fact++;
	int i;
	for(i=0;i<sibling->fill_fact;i++)
	{
		sibling->key[i] = sibling->key[i+1];
	}
	sibling->fill_fact --;
	bnode* p = sibling->parent;
	p->key[pos] = sibling->key[0];
	p->key[pos-1] = target->key[0];

}
void btree::lftdistribute(bnode* target,bnode* sibling,int pos)
{
	int tf= target->fill_fact;
	int sf = sibling->fill_fact;
	bnode* p = target->parent;
	int i=0;
	for(i=tf;i>0;i--)
	{
		target->key[i] = target->key[i-1];
	}
	target->key[0] = sibling->key[sf-1];
	sibling->key[sf-1] = -1;
	sibling->fill_fact --;
	target->fill_fact++;
	p->key[pos-1] = target->key[0];
}
int btree::splmerge(int pc,bnode* p)
{
    bnode* r=p->parent;
    int rf = r->fill_fact;
    int pf = p->fill_fact;
   
    //bnode* lftsib = r->index_ptr[pc-1];
    int i;
    if(pc != 0 && pc != r->fill_fact)
    {
          bnode* rytsib = r->index_ptr[pc+1];
          bnode* lftsib = r->index_ptr[pc-1];
          int rytsib_f = rytsib->fill_fact;
          int lftsib_f = lftsib->fill_fact;
          if(rytsib_f >= (order/2 +1))
          {
                      p->key[pf] = r->key[pc];
                      r->key[pc] = rytsib->key[0];
                      for(i=0;i<rytsib_f;i++)
                      {
                                             rytsib->key[i] = rytsib->key[i+1];
                      }
                      p->fill_fact ++;
                      rytsib->fill_fact--;
          }
          else if(lftsib_f >= (order/2 +1))
          {
               for(i=pf;i>0;i--)
               {
                                p->key[i] = p->key[i-1];
               }
               p->key[0] = r->key[pc-1];
               r->key[pc-1] = lftsib->key[lftsib_f-1];
               lftsib->key[lftsib_f-1] = -1;
               lftsib->fill_fact --;
               p->fill_fact++;
               
               
          }
          else
          {
              int j;
              p->key[pf] = r->key[pc];
              for(i= pf+1,j=0;j<rytsib_f;j++,i++)
              p->key[i] = rytsib->key[j];
              for(i=pc;i<rf;i++)
              r->key[i] = r->key[i+1];
              for(i = pc+1;i<rf;i++)
              r->index_ptr[i] = r->index_ptr[i+1];
              r->fill_fact--;
              p->fill_fact = pf+rytsib_f+1;
              if(p->fill_fact > order/2)
              return 0;
              else if(r->parent == NULL && r->fill_fact ==0)
              {
                   root = p;
                   p->parent = NULL;
                   return 0;
              }
              else if(r->parent == NULL && r->fill_fact > 0 )
              return 0;
              else
              {
                  bnode* rp = r->parent ;
                  int rpf = r->fill_fact;
                  int rpc;
                  for(i=0;i<=rpf;i++)
                  {
                                    if(rp->index_ptr[i] == r)
                                    break;
                  }
                  rpc = i;
                  splmerge(rpc,r);
              }
          }
          
          
    }
    else if(pc == 0)
    {
          bnode* rytsib = r->index_ptr[pc+1];
          int rytsib_f = rytsib->fill_fact;
          if(rytsib_f >= (order/2 +1) )
          {
                           p->key[pf] = r->key[pc];
                           r->key[pc] = rytsib->key[0];
                           for(i =0 ;i<rytsib_f;i++)
                           {
                                 rytsib->key[i] = rytsib->key[i+1];
                           }
                           rytsib->fill_fact--;
                           p->fill_fact++;                
                                                                                   
          }
          else
          {
              p->key[pf] = r->key[pc];
              int j;
              for(i = pf+1,j=0;j<rytsib_f;j++,i++)
              {
                        p->key[i] = rytsib->key[j];
              }
              p->index_ptr[pf+1] = rytsib->index_ptr[0];
              rytsib->index_ptr[0]->parent = p;
            
              for(i = pf+2,j=1;j<=rytsib_f;j++,i++)
              {p->index_ptr[i] = rytsib->index_ptr[j]; 
              rytsib->index_ptr[j]->parent = p;
              
              }
              r->fill_fact --;
              p->fill_fact = pf+rytsib_f+1;
              for(i= 0;i<rf;i++)
              r->key[i] = r->key[i+1];
              for(i = 1;i<rf;i++)
              r->index_ptr[i] = r->index_ptr[i+1];
              if(r->fill_fact > order/2)
              return 0;
               else if(r->parent == NULL && r->fill_fact == 0)
              {
                   root = p;
                   p->parent = NULL;
                   return 0;
              }
              else if(r->parent == NULL && r->fill_fact > 0)
              {
               
              return 0;
                              
              }
                               
              else 
              {
                  bnode *pp = r->parent;
                  int pct ;
                  for(i =0 ;i<= pp->fill_fact;i++)
                  {
                        if(pp->index_ptr[i] == r)
                        break;
                        }
                  pct = i;
                  splmerge(pct,r);
                  return 0;
                  
                  
                  
                  
                   
              }
              
              
          }
    }
    else //if (pc  == r->fill_fact)
    {
         bnode* lftsib = r->index_ptr[pc-1];
         int lftsib_f = lftsib->fill_fact;
         int i;
         if(lftsib_f >= (order/2 +1) )
         {
                     for(i=pf;i>0;i--)
                     {
                                      p->key[i] = p->key[i-1];
                     }
                     p->key[0] = r->key[pc-1];
                     r->key[pc-1] = lftsib->key[lftsib_f-1];
                     lftsib->key[lftsib_f-1] = -1;
                     lftsib->fill_fact--;
                     p->fill_fact++;                
                                                                                   
         }
         else
         {
             lftsib->key[lftsib_f] = r->key[pc-1];
             int j;
             for(i=lftsib_f+1,j = 0 ;j<pf;j++,i++)
             lftsib->key[i] = p->key[j];
             r->index_ptr[pc] = NULL;
             r->key[pc-1] = -1;
             r->fill_fact--;
             lftsib->fill_fact = lftsib_f+pf+1;
             for(i=lftsib_f+1,j=0;j<=pf;j++,i++)
             {
                                                lftsib->index_ptr[i] = p->index_ptr[j];
                                                p->index_ptr[j]->parent = lftsib;
             }
             if(r->fill_fact >= order/2)
             return 0;
             else if(r->parent == NULL && r->fill_fact == 0)
             {
                  root = lftsib;
                  lftsib->parent = NULL;
              }
              else if(r->parent == NULL && r->fill_fact > 0)
              return 0;
              else
              {
                  bnode* pr = r->parent;
                  int prf = pr->fill_fact;
                  int pcr ;
                  for(i =0 ;i<= prf;i++)
                  {
                        if(pr->index_ptr[i] == r)
                        break;
                        }
                  pcr = i;
                  splmerge(pcr,r);
                  return 0;   
             
         }
         
         
    }
    
}
}
int btree::rytmerge(bnode* t,bnode* sibling,int pos)
{
                int i,j;
                int tf = t->fill_fact;
                int sf = sibling->fill_fact; 
                bnode* p = t->parent;
                for(i=tf,j=0;j<sf;j++,i++)
                {
                     t->key[i] = sibling->key[j];
                }
                for(i=pos;i<p->fill_fact;i++)
                {
                     p->key[pos] = p->key[pos+1];
                                             
                }
                p->index_ptr[pos] = t;
                p->fill_fact--;
                for(i = pos+1;i<= p->fill_fact;i++)
                {
                      p->index_ptr[i] = p->index_ptr[i+1];
                }
                t->fill_fact = sf+tf;
                if(p->fill_fact >= order/2 )
                                return 0;
                else
                {
                       bnode*pp = p->parent;
                       if(pp == NULL && p->fill_fact > 0)
                             return 0;
                       else if(pp==NULL && p->fill_fact == 0)
                       {
                            root = t;
                            t->parent = NULL;
                            return 0;
                       }     
                             
                       else
                       {
                           int pc;
                           for(i=0; i<= pp->fill_fact;i++)
                           {
                                     if(pp->index_ptr[i] == p)
                                     {
                                          pc= i;
                                          break;
                                     }
                           }
                         
                          splmerge(pc,p);
                          return 0;
                          
                       }
                }   
                
                                          
}
int btree::lftmerge(bnode* t,bnode* sibling,int pos)
{
     int tf = t->fill_fact;
     int sf = sibling->fill_fact;
     bnode* p = sibling->parent;
     int i,j;
     for(i= sf,j=0;j<tf;i++,j++)
     {
            sibling->key[i] = t->key[j];
     }
     sibling->fill_fact = tf+sf;
     p->key[pos-1] = -1;
     p->index_ptr[pos] = NULL;
     p->fill_fact -- ;
     if(p->fill_fact >= order/2 )
     return 0;
     else
     {
         bnode* pp = p->parent;
         if(pp== NULL && p->fill_fact > 0 )
         return 0;
         else if( pp == NULL && p->fill_fact == 0)
         {
              root = sibling;
              sibling->parent = NULL;
              return 0;
         }
         else
         {
             int pc;
                           for(i=0; i<= pp->fill_fact;i++)
                           {
                                     if(pp->index_ptr[i] == p)
                                     {
                                          pc= i;
                                          break;
                                     }
                           }
                         
                          splmerge(pc,p);
                          return 0;
             
         }
         
     }      
     
 }
 int btree::chek_del(int po,bnode* t_l)
 {
	   bnode* p = t_l->parent;
	   int m;
	
		if(po == 0)
		{
			if(p->index_ptr[po+1]->fill_fact > order/2)
				rytdistribute(t_l,p->index_ptr[po+1],po);
			else
				m = rytmerge(t_l,p->index_ptr[po+1],po);
		}
		else if( po == p->fill_fact)
		{
			if(p->index_ptr[po-1]->fill_fact >order/2)
				lftdistribute(t_l,p->index_ptr[po-1],po);
			else 
				m= lftmerge(t_l,p->index_ptr[po-1],po);
		}
		else
		{
			if(p->index_ptr[po+1]->fill_fact  > order/2)
				rytdistribute(t_l,p->index_ptr[po+1],po);
			else if(p->index_ptr[po-1]->fill_fact >order/2)
				lftdistribute(t_l,p->index_ptr[po-1],po);
			else 
				m = rytmerge(t_l,p->index_ptr[po+1],po);

          }
		return 0;
	

	
 }
int btree::delete_key(int key)
{
	bnode* t_leaf = search_leaf(root,key);
	int pos1,i,pos;
	for(i = 0;i<t_leaf->fill_fact ; i++)
	{
		if(t_leaf->key[i] == key)
		{
			pos1 = i;
			break;
		}
	}
	for( i =pos1;i<t_leaf->fill_fact;i++)
	{
		t_leaf->key[i] = t_leaf->key[i+1];
	}
	t_leaf->fill_fact --;
	bnode* p = t_leaf->parent;
	for(i = 0;i<=p->fill_fact ; i++)
		{
			if(p->index_ptr[i] == t_leaf)
					break;
		
		}
	pos=i;
	bnode* i_entry = search_node(p->parent,key);
	if(i_entry != NULL)
	{
               for(i=0;i<i_entry->fill_fact;i++)
               {
                                                if(i_entry->key[i] == key)
                                                break;
               }
               i_entry->key[i] = t_leaf->key[0];
    }

	if(t_leaf->fill_fact >= order/2)
	{
        if (pos1==0 && pos != 0)
            p->key[pos-1] = t_leaf->key[0];
        return 0;    
		 
	}
	else
	{
	    int k = chek_del(pos,t_leaf);
	    return 0;
     }
	
}
static int level=0;
bnode* btree::show(bnode* temp)
{
	int i;
	if(temp->parent == NULL)
		cout<<endl<<"NO PARENT"<<endl;
		else 
		cout<<endl<<"PARENT IS "<<temp->parent->key[0]<<endl;
		
	cout<<"ISKA FILL FACTOR: \t"<<temp->fill_fact<<endl;	
	
	for(i=0;i<temp->fill_fact;i++)
	{
		
		cout<<"\t"<<"key "<<i<<"-> : "<<temp->key[i]<<endl;
	}
	
	return temp;
	
}
void btree::showchild(bnode * temp)
{
	int i =0;
	bnode* b;
	if(temp->index_ptr[i] != NULL)
	{	level++;
	cout<<"LEVEL : "<<level<<endl;
	
	while(temp->index_ptr[i] != NULL && i<=order)
	{
		b =	show(temp->index_ptr[i]);
		i++;
		cout<<endl;
	}
	
	}
}

void btree::display()
 {	
	 level = 0;
	 cout<<"LEVEL : "<<level;
	 cout<<endl;
	 bnode* b = show(root);
	 
	 int i=0;
	 
	 showchild(b);
	 while(b->index_ptr[i] != NULL && i<(order+1))
	 {
		 bnode* t;
		 t = b->index_ptr[i];
		 cout<<endl;
		 showchild(t);
		 i++;
 	 }
	 
 }

 int main()
 {
	int x,j,choice;
	btree b;
	b.initr();
	int a;
	char res;
	
hihi:	cout<<"Choose"<<endl;
	cout<<"\t 1.INSERT "<<endl;
	cout<<"\t 2.DELETE "<<endl;
	cout<<"\t 3.DISPLAY "<<endl;
	
	cin>>choice;
	switch(choice)
	{
                  case 1:
                       cout<<"Enter value to insert"<<endl;
                       cin>>x;
                       a = b.insert(x);
                       cout<<"INSERTING "<<x<<"......"<<endl;
                       cout<<"do you want to continue??"<<endl;
                       cin>>res;
                       if(res == 'y')
                             goto hihi;
                       else
                             break;
                       break;
                       
                  case 2:
                       cout<<"Enter Value to delete"<<endl;
                       cin>>x;
                       b.delete_key(x);
                       cout<<"DELETING "<<x<<"......"<<endl;
                       cout<<"do you want to continue??"<<endl;
                       cin>>res;
                       if(res == 'y')
                             goto hihi;
                       else
                             break;
                       break;
                  case 3:
                       cout<<"DISPLAYING........"<<endl;
                       b.display();
                       cout<<"do you want to continue??"<<endl;
                       cin>>res;
                       if(res == 'y')
                             goto hihi;
                       else
                             break;
                       break;
                  default: 
                       cout<<"do you want to continue??"<<endl;
                       cin>>res;
                       if(res == 'y')
                             goto hihi;
                       else
                             break;
    }
    getch();
	return 0;
 }


